package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/even-odd-tree/'>奇偶树(Even Odd Tree)</a>
 * <p>
 *     如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
 *     <ul>
 *         <li>二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。</li>
 *         <li>偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增</li>
 *         <li>奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减</li>
 *     </ul>
 *     给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
 *                          1
 *                       /     \
 *                      10      4
 *                     /      /   \
 *                    3      7     9
 *                   / \    /       \
 *                 12   8  6         2
 *
 *      输出：true
 *      解释：每一层的节点值分别是：
 *          0 层：[1]
 *          1 层：[10,4]
 *          2 层：[3,7,9]
 *          3 层：[12,8,6,2]
 *          由于 0 层和 2 层上的节点值都是奇数且严格递增，而 1 层和 3 层上的节点值都是偶数且严格递减，因此这是一棵奇偶树。
 *
 * 示例 2：
 *      输入：root = [5,4,2,3,3,7]
 *                          5
 *                        /   \
 *                       4     2
 *                     /  \   /
 *                    3    3 7
 *      输出：false
 *      解释：每一层的节点值分别是：
 *          0 层：[5]
 *          1 层：[4,2]
 *          2 层：[3,3,7]
 *          2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。
 *
 * 示例 3：
 *      输入：root = [5,9,1,3,5,7]
 *                          5
 *                        /   \
 *                       9     1
 *                     /  \   /
 *                    3    5 7
 *      输出：false
 *      解释：1 层上的节点值应为偶数。
 *
 * 示例 4：
 *      输入：root = [1]
 *      输出：true
 *
 * 示例 5：
 *      输入：root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
 *      输出：true
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>树中节点数在范围 [1, 10^5] 内</li>
 *      <li>1 <= Node.val <= 10^6</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/1 16:50
 */
public class LC1609EvenOddTree_M {

    static class Solution {
        public boolean isEvenOddTree(TreeNode root) {
            if (root == null) {
                return true;
            }
            // 从第0层开始
            boolean evenIndexLevel = true;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int currLevelNodeSize = queue.size();
                // 偶数层前一个节点值
                int evenPreNodeVal = Integer.MIN_VALUE;
                // 奇数层前一个节点值
                int oddPreNodeVal = Integer.MAX_VALUE;
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode currNode = queue.poll();
                    int currNodeVal = currNode.val;
                    if (evenIndexLevel) {
                        // 偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
                        if (currNodeVal % 2 == 0 || currNodeVal <= evenPreNodeVal) {
                            return false;
                        }
                        evenPreNodeVal = currNodeVal;
                    } else {
                        // 奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
                        if (currNodeVal % 2 == 1 || currNodeVal >= oddPreNodeVal) {
                            return false;
                        }
                        oddPreNodeVal = currNodeVal;
                    }
                    if (currNode.left != null) {
                        queue.offer(currNode.left);
                    }
                    if (currNode.right != null) {
                        queue.offer(currNode.right);
                    }
                }
                // 进入下一层
                evenIndexLevel = !evenIndexLevel;
            }
            return true;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(10);
        root.right = new TreeNode(4);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(12);
        root.left.left.right = new TreeNode(8);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        root.right.left.left = new TreeNode(6);
        root.right.right.right = new TreeNode(2);


        Solution solution = new Solution();
        System.out.println(solution.isEvenOddTree(root));
    }
}
